package 每日一题;

import java.util.PriorityQueue;
import java.util.TreeMap;

public class No1438绝对差不超过限制的最长连续子数组 {

    /**
     * 给你一个整数数组 nums ，和一个表示限制的整数 limit，
     * 请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。
     * 如果不存在满足条件的子数组，则返回 0 。
     *
     * 示例 1：
     * 输入：nums = [8,2,4,7], limit = 4
     * 输出：2
     * 解释：所有子数组如下：
     * [8] 最大绝对差 |8-8| = 0 <= 4.
     * [8,2] 最大绝对差 |8-2| = 6 > 4.
     * [8,2,4] 最大绝对差 |8-2| = 6 > 4.
     * [8,2,4,7] 最大绝对差 |8-2| = 6 > 4.
     * [2] 最大绝对差 |2-2| = 0 <= 4.
     * [2,4] 最大绝对差 |2-4| = 2 <= 4.
     * [2,4,7] 最大绝对差 |2-7| = 5 > 4.
     * [4] 最大绝对差 |4-4| = 0 <= 4.
     * [4,7] 最大绝对差 |4-7| = 3 <= 4.
     * [7] 最大绝对差 |7-7| = 0 <= 4.
     * 因此，满足题意的最长子数组的长度为 2 。
     * 示例 2：
     * 输入：nums = [10,1,2,4,7,2], limit = 5
     * 输出：4
     * 解释：满足题意的最长子数组是 [2,4,7,2]，其最大绝对差 |2-7| = 5 <= 5 。
     * 示例 3：
     * 输入：nums = [4,2,2,2,4,4,2,2], limit = 0
     * 输出：3
     *
     * 提示：
     * 1 <= nums.length <= 10^5
     * 1 <= nums[i] <= 10^9
     * 0 <= limit <= 10^9
     */

    //双指针超时,需要滑动窗口
    public int longestSubarray(int[] nums, int limit) {

        int left=0;
        int right=0;
        int min=0;
        int max=0;
        int result=0;

        while (right<nums.length){

            //重置
            int leftNum=nums[left];
            min=leftNum;
            max=leftNum;

            while (right<nums.length){
                int rightNum=nums[right];
                min=Math.min(min,rightNum);
                max=Math.max(max,rightNum);
                if(max-min>limit){
                    //当前右指针进入后不符合
//                    left=right;//重置,寻找min和max
                    while (nums[left]!=min&&nums[left]!=max){
                        left++;
                    }
                    right=left;
                    left=right;
                    break;
                }else{
                    //符合,右指针前进
                    result=Math.max(result,(right-left)+1);//维护结果
                    right++;
                }
            }

        }

        return result;
    }

    //滑动窗口(堆版)复杂度较高
    public int longestSubarrayGood(int[] nums, int limit) {

        int left=0;
        int right=0;
        int result=0;
        PriorityQueue<Integer> minDump=new PriorityQueue<>();
        PriorityQueue<Integer> maxDump=new PriorityQueue<>((o1,o2)->o2-o1);

        while (right<nums.length){

            while (right<nums.length){
                int rightNum=nums[right];
                minDump.add(rightNum);
                maxDump.add(rightNum);
                while (maxDump.peek()-minDump.peek()>limit){
                    //当前右指针进入后不符合
//                    left=right;//重置
                    /**
                     * 重要Api,堆的remove()方法
                     */
                    maxDump.remove(nums[left]);
                    minDump.remove(nums[left]);
                    left++;
                    //还要维护最大和最小值,吐掉的这个是最大值,那么第二个最大值是什么?吐掉的这个的最小值,那第二个最小值呢?
                }
                //符合,右指针前进
                result=Math.max(result,(right-left)+1);//维护结果
                right++;
            }

        }

        return result;

    }

    //滑动窗口(TreeMap版本)
    public int longestSubarrayBestGood(int[] nums, int limit) {

        //key:nums[i]  value:count
        TreeMap<Integer,Integer> treeMap=new TreeMap<>();

        int left=0;
        int right=0;
        int result=0;

        while (right<nums.length){

            treeMap.put(nums[right],treeMap.getOrDefault(nums[right],0)+1);

            while (treeMap.lastKey()-treeMap.firstKey()>limit){

                //返回老value
                Integer oldValue = treeMap.put(nums[left], treeMap.get(nums[left])-1);
                if(oldValue.equals(1)){
                    treeMap.remove(nums[left]);
                }
                left++;

            }

            result=Math.max(result,right-left+1);

            right++;
        }

        return result;
    }

    public static void main(String[] args) {
        No1438绝对差不超过限制的最长连续子数组 n=new No1438绝对差不超过限制的最长连续子数组();
        int[] arr={10,1,2,4,7,2};
        int result = n.longestSubarrayBestGood(arr, 5);
        System.out.println(result);
    }

}
